package meituan.summer10;

/**
 * @Author Fizz Pu
 * @Date 2021/4/14 下午5:08
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */
/*
小团有一个由N个节点组成的二叉树，每个节点有一个权值。定义二叉树每条边的开销为其两端节点权值的乘积，二叉树的总开销即每条边的开销之和。
小团按照二叉树的中序遍历依次记录下每个节点的权值，即他记录下了N个数，第i个数表示位于中序遍历第i个位置的节点的权值。之后由于某种原因，
小团遗忘了二叉树的具体结构。在所有可能的二叉树中，总开销最小的二叉树被称为最优二叉树。现在，小团请小美求出最优二叉树的总开销。
 */

import java.util.*;

public class Main4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            int[] nums = new int[n + 1];
            for (int i = 0; i < n; i++) {
                nums[i] = sc.nextInt();
            }
            Main4 main = new Main4();
            int ans = Integer.MAX_VALUE;
            int[][][] memo = new int[n + 1][n + 1][n + 1];
            for (int i = 0; i < n; i++) {
                ans = Math.min(ans,main.dfs(nums,0,i - 1,i,memo) + main.dfs(nums,i + 1,n - 1,i,memo));
            }
            System.out.println(ans);
        }
    }
    int dfs(int[] nums, int l, int r, int father, int[][][] memo) {
        if (l > r) return 0;
        if (l == r) return nums[l] * nums[father];
        if (memo[l][r][father] != 0) return memo[l][r][father];
        int res = Integer.MAX_VALUE;
        for (int i = l; i <= r; i++) {
            int left = dfs(nums, l, i - 1, i, memo);
            int right = dfs(nums, i + 1, r, i, memo);
            res = Math.min(res, left + right + nums[i] * nums[father]);
        }
        memo[l][r][father] = res;
        return res;
    }
}

